135. 分发糖果
135. 分发糖果
Similar Question
Solution Tips
方案一: 哈希表 + 暴力模拟
var candy = function (nums) {
// 先发送第一轮, 每个孩子一个糖果, 那相当于所有人都没有发
// 大家都是0也是相等的case, 直接开始发高分糖果, 最后加上1就行
// 瞻前顾后, 就怕是发了之后不平衡了, 要重新调整
// 可以想象 AVL 树, 应该是有固定的调整模式的
// 派负数糖果, 最后回正即可
// 从得分最低的孩子开始派糖果即可
// 如何一轮遍历得出顺序?
const orderMap = {};
for (let i = 0; i < nums.length; i++) {
if (!orderMap[nums[i]]) {
orderMap[nums[i]] = [i];
}
else {
orderMap[nums[i]].push(i);
}
}
const res = Array.from({ length: nums.length });
// 从最小的开始派糖果
for (const rateIndexList of Object.values(orderMap)) {
for (let i = 0; i < rateIndexList.length; i++) {
const index = rateIndexList[i];
// 注意相等的时候的 case
let left = 0;
if (nums[index] > nums[index - 1]) {
left = (res[index - 1] || 0)
}
let right = 0;
if (nums[index] > nums[index + 1]) {
right = (res[index + 1] || 0)
}
res[index] = Math.max(left, right) + 1;
}
}
return res.reduce((acc, val) => acc + val, 0);
};
console.log(candy([2,4,1,3,5,8,7]))
方案二: 优先队列 + 模拟
方案三: 贪心
先确定右边评分大于左边的情况（也就是从前向后遍历）
此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
如果 ratings[i] > ratings[i - 1] 那么 [i] 的糖 一定要比 [i - 1] 的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
再确定左孩子大于右孩子的情况（从后向前遍历）
遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
因为 rating[5] 与 rating[4] 的比较 要利用上 rating[5] 与 rating[6] 的比较结果，所以 要从后向前遍历。
如果从前向后遍历，rating[5] 与 rating[4] 的比较 就不能用上 rating[5] 与 rating[6] 的比较结果了 。如图：
所以确定左孩子大于右孩子的情况一定要从后向前遍历！
如果 ratings[i] > ratings[i + 1]，此时 candyVec[i]（第 i 个小孩的糖果数量）就有两个选择了，一个是 candyVec[i + 1] + 1（从右边这个加 1 得到的糖果数量），一个是 candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。
那么又要贪心了，局部最优：取 candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第 i 个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
所以就取 candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，candyVec[i] 只有取最大的才能既保持对左边 candyVec[i - 1] 的糖果多，也比右边 candyVec[i + 1] 的糖果多
var candy = function(ratings) {
const n = ratings.length;
const left = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
let right = 0, ret = 0;
for (let i = n - 1; i > -1; i--) {
if (i < n - 1 && ratings[i] > ratings[i + 1]) {
right++;
} else {
right = 1;
}
ret += Math.max(left[i], right);
}
return ret;
};